#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL){}
};
class leetcode {
public:
    // 1. 两数之和
    vector<int> twoSum1(vector<int> nums, int target) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++){
            auto it=hash.find(target-nums[i]);
            if(it!=hash.end()) return {it->second,i};
            hash[nums[i]]=i;
        }
        return {};
    }
    // 49. 字母异位词分组
    vector<vector<string>> groupAnagrams49(vector<string> strs){
        unordered_map<string,vector<string>> mp;
        for(string str: strs){
            string key=str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;;
        for(auto it=mp.begin();it!=mp.end();it++) ans.emplace_back(it->second);
        return ans;
    }
    //128 最长连续序列
    int longestConsecutive128(vector<int> nums){
        unordered_set<int> num_set;
        for(const int num: nums) num_set.insert(num);
        int longestStreak=0;
        for(const int num: num_set){
            if(!num_set.count(num-1)){
                int currentNum=num, currentStreak=1;
                while(num_set.count(currentNum+1)){
                    currentNum+=1;
                    currentStreak+=1;
                }
                longestStreak=max(longestStreak,currentStreak);
            }
        }
        return longestStreak;
    }
    // 283. 移动零
    void moveZeros283(vector<int> nums){
        int n=nums.size(), left=0,right=0;
        while(right<n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            } right++;
        }
        for(int i: nums) cout<<i<<" ";
    }
    // 11. 盛水最多的容器
    int maxArea(vector<int> height){
        int l=0,r=height.size()-1, ans=0;
        while(l<r){
            int area=min(height[l],height[r])*(r-l);
            ans=max(ans,area);
            if(height[l]<=height[r]) l++;
            else r--;
        } return ans;
    }
    // 15 三数之和
    vector<vector<int>> threeSum(vector<int> nums){
        int n=nums.size(); sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for(int first=0;first<n;first++){
            if(first>0&&nums[first]==nums[first-1]) continue;
            int third=n-1, target=-nums[first];
            for(int second=first+1;second<n;second++){
                if(second>first+1&&nums[second]==nums[second-1]) continue;
                while(second<third&&nums[second]+nums[third]>target) third--;
                if(second==third) break;
                if(nums[second]+nums[third]==target){
                    ans.push_back({nums[first],nums[second],nums[third]});
                }
            }
        } return ans;
    }
    // 42 接雨水
    int trap(vector<int> height){
        int n = height.size();
        if (n == 0) return 0;
        vector<int> leftMax(n); leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) leftMax[i] = max(leftMax[i - 1], height[i]);

        vector<int> rightMax(n); rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) rightMax[i] = max(rightMax[i + 1], height[i]);
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += min(leftMax[i], rightMax[i]) - height[i];
        return ans;
    }
    // 3. 无重复字符的最长子串
    int lengthOf3(string s){
        unordered_set<char> occ; int n=s.size();
        int rk=-1, ans=0;
        for(int i=0;i<n;i++){
            if(i!=0) occ.erase(s[i-1]);
            while(rk+1<n&&!occ.count(s[rk+1])){
                occ.insert(s[rk+1]); rk++;
            }
            ans=max(ans,rk-i+1);
        } return ans;
    }
    // 438 字符串中所有字母异位词
    vector<int> findAnagrams(string s,string p){
        int sLen=s.size(),pLen=p.size();
        if(sLen<pLen) return vector<int>();
        vector<int> ans; vector<int>sCount(26); vector<int>pCount(26);
        for(int i=0;i<pLen;i++){
            sCount[s[i]-'a']++;
            pCount[p[i]-'a']++;
        }
        if(sCount==pCount) ans.emplace_back(0);
        for(int i=0;i<sLen-pLen;i++){
            sCount[s[i]-'a']--;
            sCount[s[i+pLen]-'a']++;
            if(sCount==pCount) ans.emplace_back(i+1);
        } return ans;
    }
    // 560 和为k的子数组
    int subarraySum(vector<int> nums, int k){
        unordered_map<int,int> mp; mp[0]=1;
        int count=0,pre=0;
        for(auto x: nums){
            pre+=x;
            if(mp.find(pre-k)!=mp.end()) count+=mp[pre-k];
            mp[pre]++;
        } return count;
    }

    // 滑动窗口最大值
    // 最小覆盖子串
    // 最大子数组和

    // 56 合并区间
    vector<vector<int>> merge(vector<vector<int>> intervals){
        if(intervals.size()==0) return {};
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> ans;
        for(int i=0;i<intervals.size();i++){
            int L=intervals[i][0],R=intervals[i][1];
            if(!ans.size()||ans.back()[1]<L) ans.push_back({L,R});
            else {ans.back()[1]=max(ans.back()[1],R);}
        } return ans;
    }
    // 189. 轮转数组
    void rotate(vector<int> nums, int k){
        int n=nums.size();
        vector<int> newArr(n);
        for(int i=0;i<n;i++) newArr[(i+k)%n]=nums[i];
        nums.assign(newArr.begin(),newArr.end());
        for(int i: nums) cout<<i<<" ";
    }
    // 238. 除以自身以外数组的乘积
    vector<int> productExp(vector<int> nums){
        int len=nums.size(); vector<int> ans(len);
        ans[0]=1;
        for(int i=1;i<len;i++) ans[i]=nums[i-1]*ans[i-1];
        int R=1;
        for(int i=len-1;i>=0;i--){
            ans[i]=ans[i]*R; R*=nums[i];
        } return ans;
    }
    // 41 缺失的第一个正数
    int firstMissingPositive(vector<int> nums){
        int n = nums.size();
        for (int& num: nums) if (num <= 0) num = n + 1;
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) nums[num - 1] = -abs(nums[num - 1]);
        }
        for (int i = 0; i < n; ++i) if (nums[i] > 0) return i + 1;

        return n + 1;
    }

    // 73 矩阵置零
    void setZeroes(vector<vector<int>> matrix){
        int m=matrix.size(),n=matrix[0].size();
        vector<int> row(m),col(n);
        for(int i=0;i<m;i++) for(int j=0;j<n;j++)
            if(!matrix[i][j]) row[i]=col[j]=true;
        for(int i=0;i<m;i++) for(int j=0;j<n;j++)
            if(row[i]||col[j]) matrix[i][j]=0;
    }
    // 54 螺旋矩阵
    vector<int> spiralOrder(vector<vector<int>> matrix){
        int directions[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(columns));
        int total = rows * columns;
        vector<int> order(total);

        int row = 0, column = 0;
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
    // 48. 旋转图像
    void rotate(vector<vector<int>> matrix){
        int n=matrix.size();
        for(int i=0;i<n/2;i++)
            for(int j=0;j<n;j++)
                swap(matrix[i][j],matrix[n-i-1][j]);
        for(int i=0;i<n;i++)
            for(int j=0;j<i;j++)
                swap(matrix[i][j],matrix[j][i]);
    }
    // 240 搜索二维矩阵
    bool searchMatrix(vector<vector<int>> matrix, int target){
        for(auto row: matrix){
            auto it= lower_bound(row.begin(),row.end(),target);
            if(it!=row.end()&& *it==target) return true;
        } return false;
    }

    // 链表
    // 160 相交链表
    ListNode *getInersectionNode(ListNode *headA,ListNode *headB){
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }

    // 二叉树
    // 94 二叉树中序遍历
    vector<int> inorderTraversal(TreeNode* root){
        function<void(TreeNode* root, vector<int>&res)> inorder=[&](TreeNode* root, vector<int>&res)->void{
            if(!root) return;
            inorder(root->left, res);
            res.push_back(root->val);
            inorder(root->right, res);
        };
        vector<int> res;
        inorder(root, res);
        return res;
    }

    // 图
    // 200 岛屿数量
    int numIslands(vector<vector<char>> grid){
        function<void(vector<vector<char>>&grid, int r,int c)> dfs=[&](vector<vector<char>>&grid, int r,int c)->void{
            int row=grid.size(), col=grid[0].size(); grid[r][c]='0';
            if(r-1>=0&&grid[r-1][c]=='1') dfs(grid,r-1,c);
            if(r+1<row&&grid[r+1][c]=='1') dfs(grid,r+1,c);
            if(c-1>=0&&grid[r][c-1]=='1') dfs(grid,r,c-1);
            if(c+1<col&&grid[r][c+1]=='1') dfs(grid,r,c+1);

        };
        int row=grid.size(); if(!row) return 0;
        int col=grid[0].size();
        int ans =0;
        for(int r=0;r<row;r++)
            for(int c=0;c<col;c++)
                if(grid[r][c]=='1'){
                    ans++; dfs(grid,r,c);
                }
        return ans;
    }
    // 腐烂的橘子
    // 课程表
    // 实现 Trie

    // 回溯
    // 46 全排列
    vector<vector<int>> permute(vector<int> nums){
        function<void(vector<vector<int>>& res, vector<int>& output, int first, int len)> dfs=[&](vector<vector<int>>& res, vector<int>& output, int first, int len)->void{
            if (first == len) {
                res.emplace_back(output);
                return;
            }
            for (int i = first; i < len; ++i) {
                swap(output[i], output[first]);
                dfs(res, output, first + 1, len);
                swap(output[i], output[first]);
            }
        };
        vector<vector<int>> res;
        dfs(res, nums, 0, (int)nums.size());
        return res;
    }
    // 二分
    int searchInsert(vector<int> nums, int target){
//        return *lower_bound(nums.begin(),nums.end(), target);
        int n=nums.size(), left=0, right=n-1, ans=n;
        while(left<=right){
            int mid=((right-left)>>1)+left;
            if(target<=nums[mid]) {
                ans=mid; right=mid-1;
            } else left=mid+1;
        } return ans;
    }

    // 栈
    // 20 有效括号
    bool isValid(string s){
        int n=s.size(); if(n%2==1) return false;
        unordered_map<char, char> pairs={
                {')','('}, {']','['},{'}','{'}
        };
        stack<char> stk;
        for(char ch:s){
            if(pairs.count(ch)){
                if(stk.empty()||stk.top()!=pairs[ch])
                    return false;
                stk.pop();
            } else stk.push(ch);
        }
        return stk.empty();
    }
    // 最小栈
    // 字符串编码
    // 每日温度
    // 柱状图中的最大矩形


    // 堆
    // 215 数组中的第k个最大元素
    int findKthLargest(vector<int> nums, int k) {
        function<void(vector<int>& a, int i, int heapSize)> maxHeapify=[&](vector<int>& a, int i, int heapSize)->void{
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;
            if (l < heapSize && a[l] > a[largest]) {
                largest = l;
            }
            if (r < heapSize && a[r] > a[largest]) {
                largest = r;
            }
            if (largest != i) {
                swap(a[i], a[largest]);
                maxHeapify(a, largest, heapSize);
            }
        };
        auto buildMaxHeap=[&](vector<int>& a, int heapSize)->void {
            for (int i = heapSize / 2 - 1; i >= 0; --i) {
                maxHeapify(a, i, heapSize);
            }
        };

        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
    // 前k个高频元素
    // 数据流的中位数


    // 贪心
    // 121 买卖股票的最佳时机
    int maxProfit(vector<int> prices){
        int inf=1e9, minPrice=inf, maxProfit=0;
        for(int price: prices){
            maxProfit=max(maxProfit,price-minPrice);
            minPrice=min(price, minPrice);
        } return maxProfit;
    }

    // 跳跃游戏
    // 划分字母区间

    // dp
    // 70. 爬楼梯
    int climbStairs(int n){
        int p=0,q=0,r=1;
        for(int i=1;i<=n;i++){
            p=q;q=r;r=p+q;
        } return r;
    }
    // 多维dp
    // 62. 不同路径
    int uniquePath(int m,int n){
//        long long ans=1;
//        for(int x=n,y=1;y<m;x++,y++) ans=ans*x/y; return ans;
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;i++)dp[i][0]=1;
        for(int j=0;j<n;j++)dp[0][j]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m-1][n-1];
    }
    // 最小路径和
    // 最长回文子串
    // 最长公共子序列
    // 编辑距离

    // 技巧
    // 只出现一次的数字
    int singleNumber(vector<int> nums){
        int ans=0; for(int e: nums) ans^=e; return ans;}
    // 多数元素
    // 颜色分类
    // 下一个排列
    // 寻找重复数

};

int main() {
    auto a2s=[&](vector<int> arr)->string{
        ostringstream tmp;
        for(int i:arr) tmp<<i<<" ";
        return tmp.str();
    };
    auto a22s=[&](vector<vector<string>> arr)-> string{
        string tmp;
        for(vector<string> i: arr){
            for(string j: i) tmp+=j+" ";
            tmp +="|";}
        return tmp;
    };
    auto i2s=[&](vector<vector<int>> arr)-> string{
        string tmp;
        for(vector<int> i: arr) {
            tmp+=a2s(i); tmp+=" | ";
        }
        return tmp;
    };
//
    auto constructTree=[&](const vector<int>& nodes) -> TreeNode*{
        if (nodes.empty() || nodes[0] == -1) return nullptr;
        TreeNode* root = new TreeNode(nodes[0]);
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (!q.empty() && i < nodes.size()) {
            TreeNode* current = q.front();
            q.pop();
            if (i < nodes.size() && nodes[i] != -1) {
                current->left = new TreeNode(nodes[i]);
                q.push(current->left);
            }
            i++;
            if (i < nodes.size() && nodes[i] != -1) {
                current->right = new TreeNode(nodes[i]);
                q.push(current->right);
            }
            i++;
        }
        return root;
    };
    function<void(TreeNode* root)> inorderTraversal=[&](TreeNode* root) -> void {
        if (root == NULL) return;
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    };
//    5,6,1,8,4,5
    auto constructList=[&](const vector<int>& nodes)-> ListNode* {
        if (nodes.empty()) return nullptr;
        ListNode* head = new ListNode(nodes[0]);
        ListNode* current = head;
        for (size_t i = 1; i < nodes.size(); ++i) {
            current->next = new ListNode(nodes[i]);
            current = current->next;
        }
        return head;
    };
    auto printList=[&](ListNode* head)->void {
        ListNode* current = head;
        while (current != nullptr) {
            cout << current->val << " ";
            current = current->next;
        }
        cout << endl;
    };

    leetcode l = *new leetcode();
    cout<<a2s(l.twoSum1({1,2,3,4}, 4))<<endl;
    cout<<a22s(l.groupAnagrams49({"eat", "tea", "tan", "ate", "nat", "bat"}))<<endl;
    cout<<l.longestConsecutive128({100,4,200,1,3,2})<<endl;
    l.moveZeros283({0,1,0,3,12});cout<<endl;
    cout<<l.maxArea({1,8,6,2,5,4,8,3,7})<<endl;
    cout<<i2s(l.threeSum({-1,0,1,2,-1,-4}))<<endl;
    cout<<l.trap({0,1,0,2,1,0,1,3,2,1,2,1})<<endl;
    cout<<l.lengthOf3("abcabcbb")<<endl;
    cout<<a2s(l.findAnagrams("cbaebabacd", "abc"))<<endl;
    cout<<l.subarraySum({1,2,3},3)<<endl;
    cout<<i2s(l.merge({{1,3},{2,6},{8,10},{15,16}}))<<endl;
    l.rotate({1,2,3,4,5,6,7},3); cout<<endl;
    cout<<a2s(l.productExp({1,2,3,4}))<<endl;
    cout<<l.firstMissingPositive({1,2,0})<<endl;
    cout<<a2s(l.spiralOrder({{1,2,3},{4,5,6},{7,8,9}}))<<endl;
    cout<<l.searchMatrix({{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}},20)<<endl;

    cout<<"listnode >>> "<<endl;
    printList(constructList({5,6,1,8,4,5}));
//    cout<<l.getInersectionNode(constructList({5,6,1,8,4,5}),constructList({4,1,8,4,5}))->val<<endl;
    cout<<"treendoe >>> "<<endl;
    cout<<a2s(l.inorderTraversal(constructTree({1,-1,2,3})))<<endl;

    cout<<l.numIslands({{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}})<<endl;
    cout<<i2s(l.permute({1,2,3}))<<endl;
    cout<<l.searchInsert({1,3,5,6},5)<<endl;
    cout<<l.isValid("()[]{}")<<endl;
    cout<<l.findKthLargest({3,2,1,5,6,4},2)<<endl;
    cout<<l.maxProfit({7,1,5,3,6,4})<<endl;
    cout<<l.climbStairs(3)<<endl;
    cout<<l.uniquePath(3,7)<<endl;
    cout<<l.singleNumber({4,1,2,1,2})<<endl;
}
